#include "Algorithm.h"


int Algorithm::MinR()
{
	int min=INT_MAX;
	int id=0;
	for(unsigned int i=0; i<tasks.size(); i++)
	{
		if(min > tasks[i].r)
		{
			min=tasks[i].r;
			id=i;
		}
	}
	return id;
}

int Algorithm::MaxQ(std::vector<Task> &tabG)
{
	int id=0;
	int max=INT_MIN;
	for(unsigned int i=0; i<tasks.size(); i++)
	{
		if(tabG[i].q>max)
		{
			max=tabG[i].q;
			id=i;
		}
	}
	return id;
}

void Algorithm::FindTask()
{
	tabG[g2]=tasks[Rid];
	tasks[Rid].r=INT_MAX;
	g++; g2++; n--;
	Qid = MaxQ(tabG);
	Rid = MinR();
}

bool Algorithm::CmaxCalculate(int &Cmax,Task &task,int &t)
{
	bool done = false;
	if (g==0)
	{
		t=tasks[Rid].r;
	}
	else
	{
		task=tabG[Qid];
		t+=tabG[Qid].p;
		task.time=t;
		Cmax=std::max(Cmax,t+tabG[Qid].q);
		tabG[Qid].q=INT_MIN;
		Qid = MaxQ(tabG);
		g--;
		done = true;
	}
	return done;
}

int Algorithm::Schrage(bool PMT)
{
	this->tabG = std::vector<Task>(tasks.size());

	if(!PMT)
	{
		this->order = std::vector<Task>(tasks.size());
	}

	Task currentTask,eZad;
	currentTask.q=INT_MAX;
	int t=0,k=0,Cmax=0;
	g=0; g2=0;
	Rid =0; Qid =0;
		
	n = tasks.size();
	
	while (n>0 || g>0)
	{
		Rid = MinR();

		while (n>0 && tasks[Rid].r<=t)
		{
			eZad=tasks[Rid];
			FindTask();
			
			if(PMT)
			{
				if (eZad.q > currentTask.q)
				{
					currentTask.p=t-eZad.r;
					t=eZad.r;
					if (currentTask.p>0)
					{
						tabG[currentTask.id]=currentTask;
						g++;
						Qid = MaxQ(tabG);
					}
				}
			}
		}
		
		if(PMT == true)
		{
			if(CmaxCalculate(Cmax,currentTask,t)){}
		}
		else
		{
			if(CmaxCalculate(Cmax,this->order[k],t))
			{
				k++;
			}
		}
	}
	return Cmax;
}

int Algorithm::B(int &U)
{
	for(int i=tasks.size()-1;i>=0;i--)
	{
		if(order[i].time+order[i].q==U)
		{
			return i;
		}
	}
	return 0;
}

int Algorithm::A(int &U,int &b)
{
	int tmp;
	for(int i=0;i<b;i++)
	{
		tmp=0;
		for(int d=i;d<=b;d++)
		{
			tmp+=order[d].p;
		}
		if(order[i].r+tmp+order[b].q==U)
		{
			return i;
		}
	}
	return 0;
}

int Algorithm::lowBand(int &task,int &order_value,int pp,int &c,std::vector<Task> &tmpTasks)
{
	tasks=tmpTasks;
	int temp=std::max(order_value,pp);
	task=temp;
	int lb=Schrage(true);
	tasks=tmpTasks;
	task=temp;

	return lb;
}

int Algorithm::Calier()
{
	int U,a =0,b=0,c=-1,i,lb;
	int tmpU = 0;
	int r=INT_MAX;
	int q=INT_MAX;
	int p=0;
	std::vector<Task> tmpTasks = tasks;

	U=Schrage(false);

	if(U<uB)
	{
		uB=U;
		this->bestOrder = this->order;
	}

	b = B(U);
	a = A(U,a);
	c = -1;

	for(i=b; i>=a;i--)
	{
		if(order[i].q<order[b].q)
		{
			c = i;
			break;
		}
	}

	if (c == -1)
	{
		this->order = this->bestOrder;
		return U;
	}

	for(i=c+1;i<=b;i++)
	{
		r = std::min(r,order[i].r);
		q = std::min(q,order[i].q);
		p+=order[i].p;
	}
	
	lb = lowBand(tasks[order[c].id].r,order[c].r,r+p,c,tmpTasks);

	if(lb<uB)
	{

		tmpU=Calier();
		if ((tmpU!=0)&&(tmpU<U))
			U = tmpU;
	}


	lb = lowBand(tasks[order[c].id].q,order[c].q,q+p,c,tmpTasks);
	
	if(lb<uB)
	{
		tmpU=Calier();
		if ((tmpU!=0)&&(tmpU<U))
			U = tmpU;
	}

	return U;
}